package cn.xiaolang.function.data_structure;

import cn.xiaolang.function.data_structure.common.SortUtils;

/**
 * 冒泡排序：(越小或者越大的元素会慢慢浮起来，故名)
 * 1. 依次相邻两个元素比较,如果顺序错误，则互换位置
 * 2. 循环执行，直到不需要互换为止
 * <p>
 * 时间复杂度为O(n2) 稳：相同元素值的位置不会发生交换
 *
 * @author Dean
 * @date 2021-08-09
 */
public class SortByBubble {


    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 6, 2, 8, 9, 1, 7};


        //O(n)
        for (int j = 0; j < arr.length - 2; j++) {
            int cursor = 0;
            boolean isOver = true;
            // 从cursor开始依次比较相邻两个元素的大小，O(n)
            // 优化2：末尾每次会浮起一个最大值，无需再比较，第j次排，只需要检测arr.length-j的元素比较
            for (int i = 1; i < arr.length - j; i++, cursor++) {
                if (arr[cursor] > arr[i]) {
                    SortUtils.swap(arr, i, cursor);
                    isOver = false;
                }
            }
            // 优化1 ：添加完成标志，后续的循环没有必要
            if (isOver) {
                break;
            }
            SortUtils.printArr(arr);
        }


    }

}
